package binarytree

// 递归
func invertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}

	root.Left, root.Right = root.Right, root.Left
	invertTree(root.Left)
	invertTree(root.Right)
	return root

}

// 迭代
func invertTree2(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}

	stack := []*TreeNode{root}

	for len(stack) != 0 {
		temp := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		temp.Right, temp.Left = temp.Left, temp.Right
		if temp.Right != nil {
			stack = append(stack, temp.Right)
		}
		if temp.Left != nil {
			stack = append(stack, temp.Left)
		}
	}
	return root
}
